package q120_minimumTotal;

import java.util.List;

public class Solution_1 {


    /*
    此题的解法实际上是动态优化
    假设我们将三角形左端对齐 视为一个二维数组
    [2]
    [3,4]
    [6,5,7]
    [4,1,8,3]
    f(i, j)代表要从顶端走到位置i j的最小路径之和
    显然有f(i, j) = Math.min(f(i - 1, j), f(i - 1, j - 1)) + c(i, j)
    值得注意的是 对于边界 显然最左侧的只能够从上一层最左侧的移动过来 最右侧的也是如此
    最后遍历最后一行 即可得到最短路
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[n][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            // 先处理边界
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                // dp转移
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            // 最右侧也需要单独处理
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = f[n - 1][0];
        // 遍历最后一行获得答案
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }



}
